package 校招笔试.腾讯笔试.腾讯音乐;

import org.junit.Test;

import java.util.HashSet;
import java.util.Scanner;
import java.util.Set;

/**
 * @author aodre , QQ : 480029069
 * @date 2023/3/23 18:48
 */
public class Main {
    /*
    1、小红拿到了一个二叉树，二叉树共有n个节点。小红希望你将所有节点赋值为1到n的正整数，且没有两个节点的值相等。需要满足: 奇数层的权值和与偶数层的权值和之差的绝对值不超过1。
    如果有多种赋值方案，请返回任意一种方案。如果无解，请返回空树。数据范围: 1 < n < 105。给定的二叉树节点初始权值默认为-1。

    2、小红定义一个字符串的权值为:字符串长度乘以字符串的字母种类数量。例如，"abacb”的价值为5*3=15

    小红拿到了一个字符串，她准备将该字符串切分成n个子串 (将这人个子串按顺序拼在一起即可得到原串)。小红希望切分后这n个子串的最大权值尽可能小。
    你能帮帮小红吗? 你不需要给出一个方案，只需要返回最终这n个子串的最大权值即可。字符串仅包含小写字母，且长度不超过500000。k为不超过字符串长度的正整数。

    3、小红拿到了一个仅由大写字母和小写字母组成的字符串。她想知道，在不考虑大小写的情况下，有多少对相邻的字母相等?字符串长度不超过2 *10000






     */
    Scanner sc = new Scanner(System.in);

    public static void main(String[] args) {
            String s = "ababbbb";
            int k = 2;
        int judge = judge(s, 6);
        System.out.println(judge);

    }


    public int solutionThree(String str) {
        char[] chars = str.toCharArray();
        int ans = 0;
        for (int i = 1; i < str.length(); i++) {
            int temp = Math.abs(chars[i] - chars[i - 1]);
            if (temp == 0 || temp == 32) {
                ans++;
            }
        }
        return ans;
    }
    /*
    这不就是一个 最大化（最小化）极大值（极小值）
    2023/5/10主要是
    check 函数上面 进行了升级！
     */


    public int function(String s, int k) {
        int l = 0, r = 500000 * 26;

        while (l < r) {
            int mid = l + r >> 1;
            if (judge(s, mid) > k) {
                l = mid + 1;
            } else {
                r = mid;
            }
        }
        return l;
    }

    private static int judge(String s, int mid) {
        Set<Character> set = new HashSet<>();
        int ans = 0, count = 0;
        for (int i = 0; i < s.length();) {
            set.add(s.charAt(i));
            count++;
            if (set.size() * count > mid) {
                count = 0;
                set.clear();
                ans++;
            }else{
                i++;
            }
        }
        return ans + 1;
    }

    /*
     卧槽 ， 改对了！
     */
    public int solutionTwo(String s, int k) {
        char[] str = s.toCharArray();
        int l = 1,r = 5 * 100000 * 26;
//        int l = 1, r = 7 * 26;
        while (l < r) {
            int mid = l + r >> 1;
            if (check(str, mid) > k) {
                l = mid + 1;
            } else {
                r = mid;
            }
        }
        return l;
    }

    public int check(char[] str, int value) {
        int l = 0, count = 0;
        while (l < str.length) {
            Set<Character> set = new HashSet<>();
            int i;
            for (i = l; i < str.length; i++) {
                set.add(str[i]);
                if (set.size() * (i - l + 1) > value) {
                    break;
                }
            }
            count++;
            l = i;
        }
        return count;
    }

    @Test
    public void test() {
        String s = "ababbbb";
        int i = solutionTwo(s, 2);
        System.out.println(i);
    }

    /*
    (这个题怎么  越看 月抽象！？) 感觉这个题才是 最难的!
     第一题说实话， 也不是很难，
     就是 ，状态，不好， 这种笔试， 还是图书馆比较好！

     ==
     主要是， 把 1 ~ n 之间的数，分成两个 相等 子集，  **并且这两个子集的 绝对值的差值 <= 1**
     分成两个集合之后, 直接 进行bfs 进行 node 节点的 连接 就行了!

     */


}
